Теорема о транзитивном замыкании

Для любого $\rho \subseteq A^2$ отношение $\text{Cl}_T(\rho)$ существует и равно $\rho^+ = \bigcup\limits_{i=1}^{\infty} \rho^i$.

* $\rho \subseteq \rho^+$ * $\rho^+$ транзитивно: $(a, b), (b, c) \in \rho^+ \Rightarrow \exists{i, j}\mathpunct{:}~~ (a, b) \in \rho^i \text{ и } (b, c) \in \rho^j \Rightarrow (a, c) \in \rho^{i+j} \Rightarrow (a, c) \in \rho^+$ * Если $\rho \subseteq \tau$ и $\tau$ транзитивно, то $\rho^2 \subseteq \tau\mathpunct{:}$ $(a, c) \in \rho^2 \Rightarrow \exists{b}\mathpunct{:}~~ (a, b), (b, c) \in \rho \Rightarrow (a, b), (b, c) \in \tau \Rightarrow (a, c) \in \tau$ (транзитивность $\tau$) * Аналогично $\rho^3 \subseteq \tau, \rho^4 \subseteq \tau, \dots, \rho^n \subseteq \tau$ для всех $n \Rightarrow \rho^+ \subseteq \tau$ * $\rho^+$ — наименьшее транзитивное отношение, содержащее $\rho$ $\square$